package vip.xumy.learning.algorithm;

/**
 * @author:mengyxu 
 * @date:2021年3月4日
 */

public class Exercises210204 {

	/**
	 * 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w,
	 * h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
	 * 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
	 * 
	 * 说明: 不允许旋转信封。
	 * 
	 * 示例: 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为:
	 * [2,3] => [5,4] => [6,7]。
	 */

	public static int maxEnvelopes(int[][] envelopes) {
		int len = envelopes.length;
		for (int i = 0; i < len - 1; i++) {
			for (int j = i + 1; j < len; j++) {
				int[] tmp = envelopes[i];
				if (envelopes[j][0] < tmp[0] || (envelopes[j][0] == tmp[0] && envelopes[j][1] < tmp[1])) {
					envelopes[i] = envelopes[j];
					envelopes[j] = tmp;
				}
			}
		}
		int[] dp = new int[len];
		int max = 0;
		for (int i = 0; i < len; i++) {
			int tmp = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
					tmp = Math.max(tmp, dp[j] + 1);
				}
			}
			dp[i] = tmp;
			max = Math.max(tmp, max);
		}
		return max;
	}

	/**
	 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
	 */
	public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int m = nums1.length, n = nums2.length;
		int l = m + n;
		int[] arr = new int[l];
		int i = 0, j = 0;
		while (i < m || j < n) {
			int idx = i + j;
			if (i >= m) {
				arr[idx] = nums2[j];
				++j;
			} else if (j >= n) {
				arr[idx] = nums1[i];
				++i;
			} else if (nums1[i] < nums2[j]) {
				arr[idx] = nums1[i];
				++i;
			} else {
				arr[idx] = nums2[j];
				++j;
			}
		}
		int p = l / 2;
		if (l % 2 == 0) {
			return (arr[p - 1] + arr[p]) * 0.5;
		} else {
			return arr[p];
		}
	}

	/**
	 * 给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。
	 * 
	 * 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
	 * 
	 * 假设环境不允许存储 64 位整数（有符号或无符号）。
	 */

	public static int reverse(int x) {
		long l = 0;
		while (x != 0) {
			int t = x % 10;
			l = l * 10 + t;
			x /= 10;
		}
		if (l > Integer.MAX_VALUE || l < Integer.MIN_VALUE) {
			return 0;
		}
		return (int) l;
	}

	/**
	 * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
	 * 
	 * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
	 */
	public static boolean isPalindrome(int x) {
		if (x < 0) {
			return false;
		}
		long l = 0;
		int n = x;
		while (n != 0) {
			int t = n % 10;
			l = l * 10 + t;
			n /= 10;
		}
		return l == x;
	}
	
	public static int romanToInt(String s) {
		int l = s.length();
		int sum = 0;
		int per = getValue(s.charAt(0));
		for (int i = 1; i < l; i++) {
			Integer n = getValue(s.charAt(i));
			if(per >= n) {
				sum += per;
			}else {
				sum -= per;
			}
			per = n;
		}
		return sum + per;
	}
	private static int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

}
